package outoforder.leetcode01;

import java.util.ArrayDeque;

/**
 * @author shhjiang_001
 * @create 2020-07-10 21:20
 */

//
public class Solution503 {
    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        // 将数字的长度*2，通过取模，能得到超出数组原长度的值
        for (int i = 2*length-1; i >= 0 ; i--) {
            while (!deque.isEmpty() && deque.peek() <= nums[i%length]){
                deque.pop();
            }
            res[i%length] = deque.isEmpty()? -1:deque.peek();
            deque.push(nums[i%length]);
        }
        return res;
    }
}
